package main

import "fmt"

/*
	素数
	非素数：也成为合数
	求0~100内有多少个素数
*/
func main() {
	fmt.Println(Sieve(100))
	fmt.Println(Bf(100))
}

func Bf(n int) (count int) {
	for i := 2; i <= n; i++ {
		if isPrime(i) {
			count++
		}
	}
	return
}

func Sieve(n int) (count int) {
	flags := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		if !flags[i] {
			count++
			for k := 2; k*i <= n; k++ {
				flags[k*i] = true
			}
		}
	}
	return
}

func isPrime(x int) bool {
	for i := 2; i*i <= x; i++ {
		if x%i == 0 {
			return false
		}
	}
	return true
}
